package com.roamer.javase.demo.leecode;

/**
 * @author roamer
 * @version v1.0
 * @date 2021/3/24 21:30
 */
public class ClimbStairs {
    public static int find(int n) {
        // 动态规划 和爬楼梯类似
        // n为钱，数组中代表为n元时的组合数
        int[] dps = new int[n + 1];
        // 钱的种类
        int[] types = new int[]{1, 2, 3};
        //刚好可以用一个硬币凑成的情况，是一种情况
        // while i == coin :
        //dp[i] = dp[i - coin] => dp[0]
        dps[0] = 1;

        /**
         * dp方程：dp[i] += dp[i - coin];
         */

        for (int i = 1; i <= n; i++) {
            for (int t : types) {
                if (i - t < 0) {
                    break;
                }
                dps[i] = (dps[i] + dps[i - t]);
            }
        }

        return dps[n];
    }


}
